# LeetCode 264、丑数II(动态规划)

# 一、题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

# 二、题目解析

对于任意一个丑数来说,它都可以和 2、3、5 进行相乘得到一个丑, 那么每个丑数都可以得到三个数,这三个数分别属于不同的数组中。

假设当前已经知道丑数序列 nums 是这些元素:1, 2, 3, 4, 5, 6, 8, 9

1、nums2 数组存储了这个序列中所有丑数与 2 相乘的结果,nums2 = { 1 * 2 , 2 * 2 ,3 * 2 , 4 * 2 ,5 * 2 ,6 * 2 ,8 * 2,。。。}

2、nums3 数组存储了这个序列中所有丑数与 3 相乘的结果,nums3 = { 1 * 3 , 2 * 3 ,3 * 3 , 4 * 3 ,5 * 3 ,6 * 3 ,8 * 3,。。。}

3、nums5 数组存储了这个序列中所有丑数与 5 相乘的结果,nums5 = { 1 * 5 , 2 * 5 ,3 * 5 , 4 * 5 ,5 * 5 ,6 * 5 ,8 * 5,。。。}

那么,想填充 nums 的话,它的选择来源肯定只能来源于 nums2 、nums3、nums5 这三个数组。

并且 nums 序列接下来填充的数是 nums2 、nums3、nums5 这三个数组除去已经在 nums 序列的丑数时剩下的最小值。

img

也就是说,每次寻找丑数的过程是在 nums2 、nums3、nums5 这三个数组中寻找最小值的过程。

  • 1、在寻找过程中,因为丑数的序列在不断的扩充,nums2 、nums3、nums5 这三个数组也在不断的扩充。
  • 2、每次找到那个最小值之后,接下来的寻找过程应该忽略它了。

那么,现在来看 nums2 、nums3、nums5 这三个数组的起始状态,此时,丑数序列只有一个元素 ugly[0] = 1

  • nums2 :{1 * 2......}
  • nums3: {1 * 3......}
  • nums5 :{1 * 5......}

第二个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组的第一个元素的最小值。

那么,此时可以设置三个索引,分别指向 nums2、nums3、nums5 数组开始的位置。

  • index2 指向 nums2 数组
  • index3 指向 nums3 数组
  • index5 指向 nums5 数组

比较的结果是发现 1 * 2 最小,于是第二个丑数找到了,此时 ugly 就变成 { 1 , 2 } ,nums2 、nums3、nums5 这三个数组也需要得到扩充。

  • nums2 :{1 * 2 ,2 * 2 ,......}
  • nums3: {1 * 3, 2 * 3 ,......}
  • nums5 :{1 * 5, 2 * 5 ,......}

刚才我们说过,每次找到那个最小值之后,接下来的寻找过程应该忽略它了,用代码的形式来表示就是索引值向后移动。

比如在 nums2 上找到了 1 * 2 之后,index2 开始移动到 2 * 2 的位置。

第三个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组中 index2、index3、index5 指向元素的最小值。

  • index2 指向了 nums2 中的 2 * 2,即 nums2[index2]
  • index3 指向了 nums3 中的 1 * 3,即 nums3[index3]
  • index5 指向了 nums5 中的 1 * 5,即 nums5[index5]

如此不断的循环,就可以把 ugly 数组填充到 n 的位置,得到 ugly[n]。

这里需要注意到, nums2 、nums3、nums5 这三个数组并没有具体的额外创造出来,它们都在 ugly 数组中。

  • nums2 实际上就是 ugly[]*2 的结果
  • nums3 实际上就是 ugly[]*3 的结果
  • nums5 实际上就是 ugly[]*5 的结果

所以比较的过程,实际上就是比较 nums2[index2] = ugly[index2] * 2nums3[index3] = ugly[index3] * 3nums5[index5] = ugly[index5] * 5 三者大小的过程,获取到最小值就填充到 ugly 数组中,再将对应的索引向后移动,由于 nums2 、nums3、nums5 这三个数组中会存在重复元素,所以需要执行去重的操作。

img

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public int nthUglyNumber(int n) {
      
        // 设置一个数组,用来存放结果
        // nums[0] 表示第 1 个丑数,结果是 1
        // nums[1] 表示第 2 个丑数,结果是 2
        // nums[n-1] 表示第 n 个丑数,结果需要计算
        int[] nums = new int[n];

        // nums[0] 表示第 1 个丑数,结果是 1
        nums[0] = 1;

        // 对于任意一个丑数来说,它总是可以由前面的丑数与 2、3、5 其中一个进行相乘而来的
        // 那么每个丑数都可以得到三个数,这三个数分别属于不同的数组中
        // nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
        // nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
        // nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
        // nums2 按照从小到大的顺序存放了所有丑数和 2 相乘的结果
        // nums3 按照从小到大的顺序存放了所有丑数和 3 相乘的结果
        // nums5 按照从小到大的顺序存放了所有丑数和 5 相乘的结果

        // nums[i] 的值就是在这三个数组中进行挑选
        // 设置三个索引,分别指向 nums2、nums3、nums5 数组开始的位置
        // 每当 nums[i] 的值从哪个数组中获取到,该索引就在这个数组中向后移动

        // index2 指向 nums2 数组
        int index2 = 0;

        // index3 指向 nums3 数组
        int index3 = 0;

        // index5 指向 nums5 数组
        int index5 = 0;

        // 开始填充 nums 数组
        for (int i = 1; i < n; i++) {
            
            // nums[i] 的值就是在这三个数组中进行挑选最小值
            // 但是,这三个数组并没有具体的额外创造出来,它们都在 nums 数组中
            // 其中 nums[index2] 表示的就是第 index2 个丑数,nums[index2] * 2 在数组 nums2 中的位置为 index2
            // 其中 nums[index3] 表示的就是第 index3 个丑数,nums[index3] * 3 在数组 nums3 中的位置为 index3
            // 其中 nums[index5] 表示的就是第 index5 个丑数,nums[index5] * 5 在数组 nums5 中的位置为 index5
            nums[i] = Math.min(Math.min(nums[index2] * 2, nums[index3] * 3), nums[index5] * 5);

            // 执行完上面的代码之后,nums[i] 已经被填充完毕
            // 那么和它相等的数需要被挪出接下来的比较

            // nums[i] == nums[index2] * 2
            // 移动 index2 到下一个数
            if (nums[i] == nums[index2] * 2) {
                index2++;
            }

            // nums[i] == nums[index3] * 3
            // 移动 index3 到下一个数
            if (nums[i] == nums[index3] * 3) {
                index3++;
            }
            
            // nums[i] == nums[index5] * 5
            // 移动 index5 到下一个数
            if (nums[i] == nums[index5] * 5) {
                index5++;
            }
        }

        // 返回结果
        return nums[n - 1];
    }
}

# 四、复杂度分析

  • 时间复杂度 O(N) : 其中 N = n ,有个 for 循环,需遍历列表。
  • 空间复杂度 O(N) : 创造了长度为 N 的结果数组,需要使用 O(N)的额外空间。